namespace Melting
{
	///< Data to use for Radix Sort 
	struct RadixEntryPointer
	{
		union
		{ 
			UINT32 	miKey; 
			FLOAT 	mfKey;
		}; 
		void* 		mxpData;
	};
	struct RadixEntryIndex
	{
		union
		{ 
			UINT32 	miKey; 
			FLOAT 	mfKey;
		}; 
		UINT32		miIndex;
	};
	
	/// Radix Sort with 11bits radix
	template < class T >
	void 	IntRadixSort11( const T* __restrict _aUnsorted, const T* __restrict _aSorted, UINT32 _iNbEntries );

	template < class T >
	void 	FloatRadixSort11( const T* __restrict _aUnsorted, const T* __restrict _aSorted, UINT32 _iNbEntries );

	//void 	IntRadixSort11	( const RadixEntry* __restrict _aUnsorted, const RadixEntry* __restrict _aSorted, UINT32 _iNbEntries );
	//void 	FloatRadixSort11( const RadixEntry* __restrict _aUnsorted, const RadixEntry* __restrict _aSorted, UINT32 _iNbEntries );

		
	#if _WINDOWS
	#	define finline __forceinline
	#else
	#	define finline inline
	#endif

	// ================================================================================================
	// flip a float for sorting
	//  finds SIGN of fp number.
	//  if it's 1 (negative float), it flips all bits
	//  if it's 0 (positive float), it flips the sign only
	// ================================================================================================
	finline UINT32 FloatFlip(UINT32 f)
	{
		UINT32 mask = -INT32(f >> 31) | 0x80000000;
		return f ^ mask;
	}

	finline void FloatFlipX(UINT32 &f)
	{
		UINT32 mask = -INT32(f >> 31) | 0x80000000;
		f ^= mask;
	}

	// ================================================================================================
	// flip a float back (invert FloatFlip)
	//  signed was flipped from above, so:
	//  if sign is 1 (negative), it flips the sign bit back
	//  if sign is 0 (positive), it flips all bits back
	// ================================================================================================
	finline UINT32 IFloatFlip(UINT32 f)
	{
		UINT32 mask = ((f >> 31) - 1) | 0x80000000;
		return f ^ mask;
	}
}


// 
typedef const char *	cpointer;

#define PREFETCH 1

#if PREFETCH
#include <xmmintrin.h>	// for prefetch
#define pfval	64
#define pfval2	128
#define pf(x)	_mm_prefetch(cpointer(x + i + pfval), 0)
#define pf2(x)	_mm_prefetch(cpointer(x + i + pfval2), 0)
#else
#define pf(x)
#define pf2(x)
#endif 

// ---- utils for accessing 11-bit quantities
#define _0(x)	(x & 0x7FF)
#define _1(x)	(x >> 11 & 0x7FF)
#define _2(x)	(x >> 22 )

namespace Melting
{ 
	  
	// ================================================================================================
	// Main radix sort
	// ================================================================================================ 
	template < class T > 
	void 	FloatRadixSort11( const T* __restrict _aUnsorted, const T* __restrict _aSorted, UINT32 _iNbEntries )
	{
		UINT32 i;
		T *sort		= (T*)_aSorted;
		T *array	= (T*)_aUnsorted;

		// 3 histograms on the stack:
		const UINT32 kHist = 2048;
		UINT32 b0[kHist * 3];

		UINT32 *b1 = b0 + kHist;
		UINT32 *b2 = b1 + kHist;

		for (i = 0; i < kHist * 3; i++) 
		{
			b0[i] = 0;
		}
		//memset(b0, 0, kHist * 12);

		// 1.  parallel histogramming pass
		//
		for (i = 0; i < _iNbEntries; i++) 
		{
			// prefetch data
			pf(array);

			UINT32 fi = FloatFlip((UINT32&)array[i].miKey);

			b0[_0(fi)] ++;
			b1[_1(fi)] ++;
			b2[_2(fi)] ++;
		}
		
		// 2.  Sum the histograms -- each histogram entry records the number of values preceding itself.
		{
			UINT32 sum0 = 0, sum1 = 0, sum2 = 0;
			UINT32 tsum;
			for (i = 0; i < kHist; i++)
			{
				tsum = b0[i] + sum0;
				b0[i] = sum0 - 1;
				sum0 = tsum;

				tsum = b1[i] + sum1;
				b1[i] = sum1 - 1;
				sum1 = tsum;

				tsum = b2[i] + sum2;
				b2[i] = sum2 - 1;
				sum2 = tsum;
			}
		}

		// byte 0: floatflip entire value, read/write histogram, write out flipped
		for (i = 0; i < _iNbEntries; i++) 
		{
			UINT32& fi = array[i].miKey;
			FloatFlipX(fi);
			UINT32 pos = _0(fi);
			
			pf2(array);
			sort[++b0[pos]] = array[i];//fi;
		}

		// byte 1: read/write histogram, copy
		//   sorted -> array
		for (i = 0; i < _iNbEntries; i++) 
		{
			UINT32& si = sort[i].miKey;
			UINT32 pos = _1(si);
			pf2(sort);
			array[++b1[pos]] = sort[i];
		}

		// byte 2: read/write histogram, copy & flip out
		//   array -> sorted
		for (i = 0; i < _iNbEntries; i++) 
		{
			UINT32& ai = array[i].miKey;
			UINT32 pos = _2(ai);

			pf2(array);
			ai = IFloatFlip(ai);
			sort[++b2[pos]] = array[i];//IFloatFlip(ai);
		}

		// to write original:
		// memcpy(array, sorted, elements * 4);
	}

	

	// ================================================================================================
	// Main radix sort
	// ================================================================================================
	template < class T > 
	void 	IntRadixSort11( const T* __restrict _aUnsorted, const T* __restrict _aSorted, UINT32 _iNbEntries )
	{
		UINT32 i;
		T *sort		= (T*)_aSorted;
		T *array	= (T*)_aUnsorted;

		// 3 histograms on the stack:
		const UINT32 kHist = 2048;
		UINT32 b0[kHist * 3];

		UINT32 *b1 = b0 + kHist;
		UINT32 *b2 = b1 + kHist;

		for (i = 0; i < kHist * 3; i++) 
		{
			b0[i] = 0;
		}
		//memset(b0, 0, kHist * 12);

		// 1.  parallel histogramming pass
		//
		for (i = 0; i < _iNbEntries; i++) 
		{
			// prefetch
			pf(array);

	//		UINT32 fi = FloatFlip((UINT32&)array[i]);
			UINT32 fi = array[i].miKey;

			b0[_0(fi)] ++;
			b1[_1(fi)] ++;
			b2[_2(fi)] ++;
		}
		
		// 2.  Sum the histograms -- each histogram entry records the number of values preceding itself.
		{
			UINT32 sum0 = 0, sum1 = 0, sum2 = 0;
			UINT32 tsum;
			for (i = 0; i < kHist; i++) 
			{ 
				tsum = b0[i] + sum0;
				b0[i] = sum0 - 1;
				sum0 = tsum;

				tsum = b1[i] + sum1;
				b1[i] = sum1 - 1;
				sum1 = tsum;

				tsum = b2[i] + sum2;
				b2[i] = sum2 - 1;
				sum2 = tsum;
			}
		}

		// byte 0: floatflip entire value, read/write histogram, write out flipped
		for (i = 0; i < _iNbEntries; i++) 
		{ 
			UINT32 fi = array[i].miKey;
	//		FloatFlipX(fi);
			UINT32 pos = _0(fi);
			
			pf2(array);
			sort[++b0[pos]] = array[i];//fi;
		}

		// byte 1: read/write histogram, copy
		//   sorted -> array
		for (i = 0; i < _iNbEntries; i++) 
		{
			UINT32 si = sort[i].miKey;
			UINT32 pos = _1(si);
			pf2(sort);
			array[++b1[pos]] = sort[i];//si;
		}

		// byte 2: read/write histogram, copy & flip out
		//   array -> sorted
		for (i = 0; i < _iNbEntries; i++) 
		{
			UINT32 ai = array[i].miKey;
			UINT32 pos = _2(ai);

			pf2(array);
			sort[++b2[pos]] = array[i];//ai;// IFloatFlip(ai);
		}
		
		//UINT32 prev = 0;
		//for (i = 0; i < kHist && prev < _iNbEntries - 1; i++) 
		//{ 
		//	prev = b1[i];
		//	LOG("Histo2 [%d] = %d\n", i, b1[i]);
		//}

		// to write original:
		// memcpy(array, sorted, elements * 4);
	} 

}